Search Results

Documents authored by Borndörfer, Ralf

Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2023.3
Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization (Short Paper)

Authors: Ralf Borndörfer, Fabian Danecker, and Martin Weiser

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.
Cite as

Ralf Borndörfer, Fabian Danecker, and Martin Weiser. Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 3:1-3:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2023.3,
  author =	{Bornd\"{o}rfer, Ralf and Danecker, Fabian and Weiser, Martin},
  title =	{{Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{3:1--3:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.3},
  URN =		{urn:nbn:de:0030-drops-187642},
  doi =		{10.4230/OASIcs.ATMOS.2023.3},
  annote =	{Keywords: shortest path, flight planning, free flight, optimal control, global optimization, Newton’s method}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.13
Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization

Authors: Boris Grimm, Ralf Borndörfer, and Julian Bushe

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances.
Cite as

Boris Grimm, Ralf Borndörfer, and Julian Bushe. Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grimm_et_al:OASIcs.ATMOS.2023.13,
  author =	{Grimm, Boris and Bornd\"{o}rfer, Ralf and Bushe, Julian},
  title =	{{Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{13:1--13:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.13},
  URN =		{urn:nbn:de:0030-drops-187741},
  doi =		{10.4230/OASIcs.ATMOS.2023.13},
  annote =	{Keywords: Railway Rolling Stock Optimization, Integer Programming, Column Generation}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2023.15
Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (Short Paper)

Authors: Fabian Löbel, Ralf Borndörfer, and Steffen Weider

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.
Cite as

Fabian Löbel, Ralf Borndörfer, and Steffen Weider. Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 15:1-15:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2023.15,
  author =	{L\"{o}bel, Fabian and Bornd\"{o}rfer, Ralf and Weider, Steffen},
  title =	{{Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{15:1--15:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.15},
  URN =		{urn:nbn:de:0030-drops-187765},
  doi =		{10.4230/OASIcs.ATMOS.2023.15},
  annote =	{Keywords: Electric Vehicle Scheduling, Battery Powered Vehicles, Charging Process, Non-linear Charging, Recharge Modeling, Dynamic Recharge Rate}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.1
An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

Authors: Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.
Cite as

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2022.1,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Maristany de las Casas, Pedro},
  title =	{{An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1},
  URN =		{urn:nbn:de:0030-drops-171052},
  doi =		{10.4230/OASIcs.ATMOS.2022.1},
  annote =	{Keywords: shortest path problem, a-star algorithm, flight trajectory optimization, flight planning, heuristics}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.2
A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization

Authors: Ralf Borndörfer, Fabian Danecker, and Martin Weiser

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen’s algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.
Cite as

Ralf Borndörfer, Fabian Danecker, and Martin Weiser. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2022.2,
  author =	{Bornd\"{o}rfer, Ralf and Danecker, Fabian and Weiser, Martin},
  title =	{{A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{2:1--2:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.2},
  URN =		{urn:nbn:de:0030-drops-171068},
  doi =		{10.4230/OASIcs.ATMOS.2022.2},
  annote =	{Keywords: shortest path, flight planning, free flight, discretization error bounds, optimal control, discrete optimization, global optimization}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2021.17
Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper)

Authors: Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
Cite as

Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer. Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17,
  author =	{\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf},
  title =	{{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17},
  URN =		{urn:nbn:de:0030-drops-148863},
  doi =		{10.4230/OASIcs.ATMOS.2021.17},
  annote =	{Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.27
Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs

Authors: Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, and Ziena Zeif

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i.
Cite as

Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, and Ziena Zeif. Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:LIPIcs.APPROX/RANDOM.2021.27,
  author =	{Bornd\"{o}rfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena},
  title =	{{Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.27},
  URN =		{urn:nbn:de:0030-drops-147200},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.27},
  annote =	{Keywords: connected partition, Gy\H{o}ri-Lov\'{a}sz, balanced partition, approximation algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.1
A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance

Authors: Boris Grimm, Ralf Borndörfer, Markus Reuther, and Thomas Schlechte

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.
Cite as

Boris Grimm, Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grimm_et_al:OASIcs.ATMOS.2019.1,
  author =	{Grimm, Boris and Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas},
  title =	{{A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{1:1--1:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.1},
  URN =		{urn:nbn:de:0030-drops-114136},
  doi =		{10.4230/OASIcs.ATMOS.2019.1},
  annote =	{Keywords: Railway Operations Research, Integer Programming, Infeasible Path Cuts, Cut Separation, Rolling Stock Rotation Problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.12
A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks

Authors: Ricardo Euler and Ralf Borndörfer

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries.
Cite as

Ricardo Euler and Ralf Borndörfer. A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{euler_et_al:OASIcs.ATMOS.2019.12,
  author =	{Euler, Ricardo and Bornd\"{o}rfer, Ralf},
  title =	{{A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{12:1--12:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.12},
  URN =		{urn:nbn:de:0030-drops-114243},
  doi =		{10.4230/OASIcs.ATMOS.2019.12},
  annote =	{Keywords: shortest path, public transit, optimization, price-sensitive, raptor, fare, operations research}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2018
OASIcs, Volume 65, ATMOS'18, Complete Volume

Authors: Ralf Borndörfer and Sabine Storandt

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
OASIcs, Volume 65, ATMOS'18, Complete Volume
Cite as

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{borndorfer_et_al:OASIcs.ATMOS.2018,
  title =	{{OASIcs, Volume 65, ATMOS'18, Complete Volume}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018},
  URN =		{urn:nbn:de:0030-drops-97272},
  doi =		{10.4230/OASIcs.ATMOS.2018},
  annote =	{Keywords: Theory of computation, Design and analysis of algorithms, Mathematics of computing, Discrete mathematics, Mathematics of computing, Combinatorics}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Ralf Borndörfer and Sabine Storandt

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.0,
  author =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.0},
  URN =		{urn:nbn:de:0030-drops-97050},
  doi =		{10.4230/OASIcs.ATMOS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.16
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable

Authors: Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.
Cite as

Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.16,
  author =	{Bornd\"{o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels},
  title =	{{A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{16:1--16:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.16},
  URN =		{urn:nbn:de:0030-drops-97214},
  doi =		{10.4230/OASIcs.ATMOS.2018.16},
  annote =	{Keywords: Vehicle Scheduling, Periodic Timetabling, Bipartite Matching}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.15
Cost Projection Methods for the Shortest Path Problem with Crossing Costs

Authors: Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that transforms crossing costs into shadow costs on individual arcs, thus approximating the SPPCC by a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
Cite as

Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach. Cost Projection Methods for the Shortest Path Problem with Crossing Costs. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2017.15,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Dung Ho\`{a}ng, Nam and Kaier, Anton and Casas, Pedro M. and Schlechte, Thomas and Schlobach, Swen},
  title =	{{Cost Projection Methods for the Shortest Path Problem with Crossing Costs}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{15:1--15:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.15},
  URN =		{urn:nbn:de:0030-drops-78939},
  doi =		{10.4230/OASIcs.ATMOS.2017.15},
  annote =	{Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.12
Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind

Authors: Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.
Cite as

Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2016.12,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schienle, Adam and Schlechte, Thomas and Schlobach, Swen},
  title =	{{Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{12:1--12:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.12},
  URN =		{urn:nbn:de:0030-drops-65360},
  doi =		{10.4230/OASIcs.ATMOS.2016.12},
  annote =	{Keywords: shortest path problem, A*, flight trajectory optimization, preprocessing, contraction hierarchies, time-dependent shortest path problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.21
Separation of Cycle Inequalities for the Periodic Timetabling Problem

Authors: Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.
Cite as

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Separation of Cycle Inequalities for the Periodic Timetabling Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:LIPIcs.ESA.2016.21,
  author =	{Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika},
  title =	{{Separation of Cycle Inequalities for the Periodic Timetabling Problem}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.21},
  URN =		{urn:nbn:de:0030-drops-63722},
  doi =		{10.4230/LIPIcs.ESA.2016.21},
  annote =	{Keywords: periodic timetabling, cycle inequalities, separation algorithm}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.111
Regional Search for the Resource Constrained Assignment Problem

Authors: Ralf Borndörfer and Markus Reuther

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider.
Cite as

Ralf Borndörfer and Markus Reuther. Regional Search for the Resource Constrained Assignment Problem. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 111-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2015.111,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus},
  title =	{{Regional Search for the Resource Constrained Assignment Problem}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{111--129},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.111},
  URN =		{urn:nbn:de:0030-drops-54536},
  doi =		{10.4230/OASIcs.ATMOS.2015.111},
  annote =	{Keywords: assignment problem, local search, branch and bound, rolling stock rota- tion problem, vehicle routing problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.79
A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem

Authors: Ralf Borndörfer, Markus Reuther, and Thomas Schlechte

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
Cite as

Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 79-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2014.79,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas},
  title =	{{A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation  Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{79--91},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.79},
  URN =		{urn:nbn:de:0030-drops-47549},
  doi =		{10.4230/OASIcs.ATMOS.2014.79},
  annote =	{Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.68
A Configuration Model for the Line Planning Problem

Authors: Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.
Cite as

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. A Configuration Model for the Line Planning Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 68-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2013.68,
  author =	{Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika},
  title =	{{A Configuration Model for the Line Planning Problem}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{68--79},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.68},
  URN =		{urn:nbn:de:0030-drops-42451},
  doi =		{10.4230/OASIcs.ATMOS.2013.68},
  annote =	{Keywords: Combinatorial optimization, polyhedral combinatorics, line planning}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.47
A Direct Connection Approach to Integrated Line Planning and Passenger Routing

Authors: Ralf Borndörfer and Marika Karbstein

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
Cite as

Ralf Borndörfer and Marika Karbstein. A Direct Connection Approach to Integrated Line Planning and Passenger Routing. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 47-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2012.47,
  author =	{Bornd\"{o}rfer, Ralf and Karbstein, Marika},
  title =	{{A Direct Connection Approach to Integrated Line Planning and Passenger Routing}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{47--57},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.47},
  URN =		{urn:nbn:de:0030-drops-37027},
  doi =		{10.4230/OASIcs.ATMOS.2012.47},
  annote =	{Keywords: combinatorial optimization, line planning, transfers, passenger routing}
}
Document
DOI: 10.4230/OASIcs.SCOR.2012.1
A Case Study on Optimizing Toll Enforcements on Motorways

Authors: Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat

Published in: OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)

Abstract
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.
Cite as

Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat. A Case Study on Optimizing Toll Enforcements on Motorways. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.SCOR.2012.1,
  author =	{Bornd\"{o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar},
  title =	{{A Case Study on Optimizing Toll Enforcements on Motorways}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Ravizza, Stefan and Holborn, Penny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.1},
  URN =		{urn:nbn:de:0030-drops-35418},
  doi =		{10.4230/OASIcs.SCOR.2012.1},
  annote =	{Keywords: Vehicle Routing Problem, Duty Rostering, Integer Programming, Operations Research}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.146
A Hypergraph Model for Railway Vehicle Rotation Planning

Authors: Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
Cite as

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider. A Hypergraph Model for Railway Vehicle Rotation Planning. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 146-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2011.146,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen},
  title =	{{A Hypergraph Model for Railway Vehicle Rotation Planning}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{146--155},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.146},
  URN =		{urn:nbn:de:0030-drops-32746},
  doi =		{10.4230/OASIcs.ATMOS.2011.146},
  annote =	{Keywords: Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.13
Railway Track Allocation by Rapid Branching

Authors: Ralf Borndörfer, Thomas Schlechte, and Steffen Weider

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
Cite as

Ralf Borndörfer, Thomas Schlechte, and Steffen Weider. Railway Track Allocation by Rapid Branching. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 13-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2010.13,
  author =	{Bornd\"{o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen},
  title =	{{Railway Track Allocation by Rapid Branching}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{13--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.13},
  URN =		{urn:nbn:de:0030-drops-27465},
  doi =		{10.4230/OASIcs.ATMOS.2010.13},
  annote =	{Keywords: track allocation problem, integer programming, rapid branching heuristic, proximal bundle method}
}
Document
DOI: 10.4230/DagSemProc.09261.15
Line Planning and Connectivity

Authors: Ralf Borndörfer, Marika Neumann, and Marc E. Pfetsch

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
The line planning problem in public transport deals with the construction of a system of lines that is both attractive for the passengers and of low costs for the operator. In general, the computed line system should be connected, i.e., for each two stations there have to be a path that is covered by the lines. This subproblem is a generalization of the well-known Steiner tree problem; we call it the Steiner connectivity Problem. We discuss complexity of this problem, generalize the so-called Steiner partition inequalities and give a transformation to the directed Steiner tree problem. We show that directed models provide tight formulations for the Steiner connectivity problem, similar as for the Steiner tree problem.
Cite as

Ralf Borndörfer, Marika Neumann, and Marc E. Pfetsch. Line Planning and Connectivity. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:DagSemProc.09261.15,
  author =	{Bornd\"{o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc E.},
  title =	{{Line Planning and Connectivity}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.15},
  URN =		{urn:nbn:de:0030-drops-21661},
  doi =		{10.4230/DagSemProc.09261.15},
  annote =	{Keywords: Steiner tree, generalization, paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1583
Line Planning on Paths and Tree Networks with Applications to the Quito Trolebús System

Authors: Luis M. Torres, Ramiro Torres, Ralf Borndörfer, and Marc E. Pfetsch

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebús system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebús System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
Cite as

Luis M. Torres, Ramiro Torres, Ralf Borndörfer, and Marc E. Pfetsch. Line Planning on Paths and Tree Networks with Applications to the Quito Trolebús System. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{torres_et_al:OASIcs.ATMOS.2008.1583,
  author =	{Torres, Luis M. and Torres, Ramiro and Bornd\"{o}rfer, Ralf and Pfetsch, Marc E.},
  title =	{{Line Planning on Paths and Tree Networks with Applications to the Quito Troleb\~{A}ƒ\^{A}ºs System}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1583},
  URN =		{urn:nbn:de:0030-drops-15838},
  doi =		{10.4230/OASIcs.ATMOS.2008.1583},
  annote =	{Keywords: Line planning, computational complexity, public transport, combinatorial optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1170
05. Models for Railway Track Allocation

Authors: Ralf Borndörfer and Thomas Schlechte

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
The optimal track allocation problem (OPTRA) is to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations for this problem: a standard formulation that models block conflicts in terms of packing constraints, and a novel formulation of the `extended' type that is based on additional `configuration' variables. The packing constraints in the standard formulation stem from an interval graph and can therefore be separated in polynomial time. It follows that the LP-relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the LP-relaxation of the extended formulation can also be solved in polynomial time, and that it produces the same LP-bound. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view. It features a constant number of rows and is amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hanover-Fulda-Kassel region of the German long distance railway network are reported.
Cite as

Ralf Borndörfer and Thomas Schlechte. 05. Models for Railway Track Allocation. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 62-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2007.1170,
  author =	{Bornd\"{o}rfer, Ralf and Schlechte, Thomas},
  title =	{{05. Models for Railway Track Allocation}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{62--78},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1170},
  URN =		{urn:nbn:de:0030-drops-11701},
  doi =		{10.4230/OASIcs.ATMOS.2007.1170},
  annote =	{Keywords: Track allocation, train timetabling,integer programming, column generation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact